Discrete Fourier Analysis and Applications

CS 8803 / MATH 8833

Spring 2012

Instructors
-Description-

Discrete Fourier analysis provides a set of techniques that have found wide applicability in mathematics and computer science. The underlying insight is that the projection of functions onto the Fourier basis can often provide the right angle in analyzing properties of various mathematical objects, such as boolean functions, graphs, PRGs, and sets of integers.

Topics will include (but are not limited to):

  • Learning theory
  • Social choice theory
  • Hypercontractivity
  • Property testing and applications to PCP's and hardness of approximation
  • Threshold phenomena in random graphs and random CSP's

Students will be expected to read and present a paper to the class.

Wednesdays, 1:00 - 4:00pm. Klaus 2108.

Schedule
  • Jan. 10 Organization, pick a course meeting time

    9:35 am, Cherry Emmerson building, room 322

  • Jan. 13Introduction & Basics

    9:30 am, Klaus 2108. ref: RO Ch1 , GK Lec. 3

  • Jan. 20Social Choice, Influence, Noise Stability

    9:30 am, Klaus 2108. ref: RO Ch2 , RO Survey

  • Jan. 25 Linearity & Dictator Testing

    Wednesday, 1:00 pm, Klaus 2108. ref: DvM Lec 4 , DvM Lec 5, RO Lec 4

  • Feb. 1 Learning, part 1

    Low-degree algorithm, Goldreich-Levin, RO, ch 3

  • Feb. 8 Learning, part 2

    Statistical Queries, lower bounds

  • Feb. 15 Hypercontractivity and KKL, Friedgut, FKN theorems
  • Feb. 22 Introduction to hardness of approximation

    PCP theorem, UGC, the Long Code, and some history

  • Feb. 29 Hardness of Approximation: MAX 3-SAT and MAX-CUT

    Arindam Khan and Anand Louis

  • Mar. 7 SDP's and harmonic analysis

    Cristobal Guzman, following Frank Vallentin's notes. Cristobal's slides

  • Mar. 14 Applications to Extremal Combinatorics

    Diego Moran, following Alon, Dinur, Friedgut, Sudakov Graph Products and Fourier Analysis

  • Mar. 28 More Extremal Combinatorics

    Ioannis Panageas, following Friedgut's On the measure of intersecting families..

  • Apr. 4 Sharp Thresholds

    Abhishek Banerjee and Pushkar Tripathi

  • Apr. 11 Percolation

    Andreas Galanis

  • Apr. 18 Additive Combinatorics

    following: RO lecture 27

  • Apr. 25 Quantum communication complexity

    Ning Tan following Gavinsky et al.

References
Course Notes
Surveys
Fourier Analysis of Boolean Functions
Harmonic Analysis on Groups
Social Choice Theory
Applications to Hardness of Approximation
Applications to Learning
Applications to Property Testing
Sharp Thresholds
Applications to Percolation
Applications to Combinatorics
Applications to Number Theory
SDP's and Harmonic Analysis
Open Problems